package com.beimihu.leetcode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeElementsSumToZero {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for(int i = 0 ; i < nums.length - 1; i ++){
            if ( i > 0 && (nums[i] != nums[i-1])){
                int p = i + 1;
                int q = nums.length - 1;
                int sum = -nums[i];

                if(nums[p] + nums[q] == sum){
                    result.add(Arrays.asList(nums[i],nums[p],nums[q]));
                }
                else if (nums[p] + nums[q] > sum){
                    while (p < q && nums[q] == nums[q-1])
                        q--;
                }
                else{
                    while (p < q && nums[p] == nums[p - 1]){
                        p++;
                    }
                }
            }
        }

        return  result;
    }
}
